/*
设 n 的长度为 x，那么 n =(10^x-1)/9
n是k的倍数，等价于 10”-1是 9k 的倍数 即10^x=1(mod 9k).
结论:最小的x必然是phi(9k)的因子。反证:如果 (9k)= px+r(0<r<x)，
根据欧拉定理10^(phi(9k))=((10)^x)^p*10^r= 10^r=1(mod 9k)这说明有一个比x更小的r，矛盾。

那么计算phi(9k)并枚举其因子d,用快速幂判断 (10^d)mod(9k)是否等于 1。
这一做法只需要O(sqrt(k)logk)的时间。
*/
class Solution {
public:
    using ll=long long;
    int phi(int n) { //计算欧拉函数(n以内与n互质的数的个数)
        int res=n;
        for(int i=2; i*i<=n; i++) {
            if(n%i==0) {
                res=res/i*(i-1);
                while(n%i==0) n/=i;
            }
        }
        if(n>1) res=res/n*(n-1);
        return res;
    }

    ll qmi(ll base, int index, ll mod) {
        ll res=1;
        while(index) {
            if(index&1) res=res*base%mod;
            index>>=1;
            base=base*base%mod;
        }
        return res;
    }

    int smallestRepunitDivByK(int k) {
        if(k%2==0|k%5==0) return -1;
        int m=phi(k*9);

        int i=1;
        for(; i*i<=m; i++) //从小到大枚举不超过sqrt(m)的因子
            if(m%i==0&&qmi(10, i, k*9)==1) return i;
        
        for(i--; ; i--) 
            if(m%i==0&&qmi(10, m/i, k*9)==1) return m/i;
        return -1;
    }
};